TOC-Context Free Language

Context Free Language

A context-free grammar (CFG) is a 4-tuple $(N,T,R,s)$, where

• $N$ is a finite set called variables;
• $T$ is a finite set called terminals;
• $R$ is a finite set of production rules with each in the form

$$A\to t_1{t}_2\cdots t_n$$

where $A$ is a variable and $t_1{t}_2\cdots t_n$ is a string of variables and terminals; and

• $s\in N$ is the start variable.

+ Definition: CFL

A language is context-free if exactly all strings in the language can be produced by a context-free grammar.

+ Theorem

A language is context-free if and only if it is recognized by a PDA.

Ambiguous

A parse tree shows the structure of a string (sentence). However, CFG is strongly enough to create ambiguous.

+ Definition: Ambiguous

A grammar is ambiguous if a string in the language defined by the grammar can be presented by multiple parse trees with different structures.

Also, checking whether a CFG is ambiguous is undecidable. Meaning that there is NO algorithm / machine which can tell an arbitrary CFG is ambiguous or not.

Properties

Equivalence

+ Theorem

A language is context-free if and only if it is recognized by a PDA.

Let $L$ be an arbitrary context-free language. By the definition of CFL, $L$ has a CFG $G$ generating it. Then, we prove the theorem by introducing a conversion algorithm from $G$ to a PDA $P$ which recognizes $L$ and vice versa.

CFG to PDA

To construct the PDA $P$ from $G$, let w be a string in L.

• $G$ generates $w$ by a sequence of productions.
• We construct $P$ to simulate this procedure.
• $P$ generates some strings and pushes them into the stack.
• Then, $P$ tries to match the stack with $w$.

In detail, P does the following things.

1. Push $ and the start variable $E$ into the stack ($ first and E second).
2. Repeat the followings.
   • If a variable $A$ is on top of the stack, nondeterministically select the rules starts from A and replace A by the RHS of the rule (in the stack).
   • If a terminal a is on top of the stack, check the next input symbol. If yes, continue; otherwise reject.
   • If $ is on the top, accept the string if all symbols of w have been read; reject otherwise.

Formally, let $G=(N,T,R,s)$ be a CFG. Construct the following transitions.

1. $\delta (q_{start},ϵ,ϵ)=(q_E,\mathrm{\$})$
2. $\delta (q_E,ϵ,ϵ)=(q_{loop},E)$
3. $\delta (q_{loop},ϵ,\mathrm{\$})=(q_{accept},ϵ)$
4. For each production rule $r$ in the form of $A\to t_1{t}_2\cdots t_n$, where $n\ge 2$; construct the followings:
   • 1. $\delta (q_{loop},ϵ,A)=(r_1,t_n)$;
   • 2. $\delta (r_i,ϵ,ϵ)=(r_{i+1},t_{n-i})$ for $1\le i\le n-2$
   • 3. $\delta (r_{n-1},ϵ,ϵ)=(q_{loop},t_1)$
5. For each production rule $A\to t,\delta (q_{loop},a,a)=(q_{loop},t)$.
6. For each terminal $a\in T,\delta (q_{loop},a,a)=(q_{loop},ϵ)$.

The PDA is called parser, which is used in compilers.

PDA to CFG

Now let's convert an arbitrary PDA $P^{\prime }$ to a CFG $G^{\prime }$. First, we modify $P^{\prime }$.

• $P^{\prime }$ has a single final state $q_f$. If it has multiple accepting states, create some artificial $ϵ$ transitions to one of the accepting states.
• The stack of $P^{\prime }$ is always empty when a string is accepted. If the stack is non-empty, create an artificial state to pop out everything in the state.
• Every transition either pushes a symbol or pops out a symbol (not both, not none). If a transition is $\delta (q_i,a,x)=(q_i,y)$, create an artificial state $q_k$ and replace the transition by $\delta (q_i,a,x)=(q_k,ϵ)$ and $(q_k,ϵ,ϵ)=(q_j,y)$

Formally, Let $P^{\prime }=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_f)$. The construction of $G^{\prime }$ is as follows:

• The set of nonterminals is $N=\{A_{i,j}\mid q_i,q_j\in Q\}$.
• The set of terminals is $T=\mathrm{\Sigma }$.
• The initial symbol is $s=A_{0,f}$.
• The production rules are of three types:
  • $\mathrm{\forall }x\in \mathrm{\Gamma }$, if there exist transitions $\delta (q_i,a,\epsilon )=(q_j,x)$ and $\delta (q_k,b,x)=(q_l,\epsilon )$, then add $A_{i,l}\to a{A}_{j,k}b$ to $R$.
  • $\mathrm{\forall }{q}_i,q_j,q_k\in Q$, add $A_{i,j}\to A_{i,k}{A}_{k,j}$ to $R$.
  • $\mathrm{\forall }{q}_i\in Q$, add $A_{i,i}\to \epsilon$.

Limitation

Closure Properties

Context-free and Regular